# 动态规划 空间换时间 又称 带备忘录的递归 递归树的剪枝
# 动态规划思路    暴力递归   记忆化搜索   改为迭代算法



memo = {}

def L(nums, i):
    if i in memo:
        return memo[i]


    if i == len(nums) - 1:
        return 1

    max_len = 1
    for j in range(i + 1, len(nums)):
        if nums[j] > nums[i]:
            max_len = max(max_len, L(nums, j) + 1)

    memo[i] = max_len
    return max_len


if __name__ == '__main__':
    nums = [1, 5, 2, 4, 3]
    print(max(L(nums, i) for i in range(len(nums))))
